﻿namespace Graph;

//QuickFind
public class UnionFindSet : IUF
{
    private int[] ids; //记录每个顶点所属集合的编号

    public UnionFindSet(int size)  //size：顶点数量
    {
        ids = new int[size];

        for (int i = 0; i < size; i++)
        {
            ids[i] = i;  //i号顶点所属集合编号设为i；
        }
    }

    public int Size => ids.Length;

    //查找顶点p所属集合编号 O（1）
    private int Find(int p)
    {
        return ids[p];
    }

    //查看顶点p，q是否联通（属于同一集合） O（1）
    public bool IsConnected(int p, int q)
    {
        return Find(p) == Find(q);
    }

    //合并p，q 所在集合 O（n），可优化！
    public void Union(int p, int q)
    {
        int pId = Find(p);
        int qId = Find(q);

        if (pId == qId)
        {
            return;
        }

        for (int i = 0; i < ids.Length; i++)
        {
            if (ids[i] == pId)
            {
                ids[i] = qId;
            }
        }
    }
}
